\begin{table}
  \centering          
  \caption{Control costs. The first four entries indicate a minimum level of control quality in four base configurations. Control quality is improved (cost is reduced) for additional available nodes.}
  \label{tab:configurationcosts}
  \centering  
  \begin{tabular}{cc}
    \hline
    $\nodeconfig$ & $\controlcost^\nodeconfig$ \\
    \hline
    $\{\node_A,\node_C\}$ & 5.3 \\
    $\{\node_A,\node_D\}$ & 6.4 \\
    $\{\node_B,\node_C\}$ & 7.5 \\
    $\{\node_C,\node_D\}$ & 5.7 \\
    \hline
    $\{\node_A,\node_B,\node_C\}$ & 4.3 \\
    $\{\node_A,\node_B,\node_D\}$ & 3.1 \\
    \hline
  \end{tabular}
\end{table}



\section{Design Space Exploration} \label{sec:dse}
\noindent
The synthesized solutions (mappings, schedules, and controllers) for
base configurations cover all specified fault scenarios, but provide
only a certain minimum level of control quality. It is important to
note that this quality level is not degraded with the number of failed
nodes, as long as we are only considering feasible configurations.  In
this section, we shall consider the synthesis of solutions for
additional configurations in order to improve upon the minimum level
of control quality provided by the base configurations. In this way,
the system can provide better control quality for some selected
feasible configurations in addition to the base configurations.  We
shall first resume our running example to motivate such quality
improvements. Section~\ref{sec:problemstatement} presents a formal
problem statement. Section~\ref{sec:heuristic} presents our proposed
algorithm that selects additional feasible configurations and
optimizes their control quality.




\subsection{Motivational example}
\noindent
We shall continue our example from Section~\ref{sec:baseconfigexample}
with
\begin{displaymath}
  \baseconfigset = \{
  \{\node_A, \node_C\}, \{ \node_B, \node_C\}, \{\node_C, \node_D\},
  \{\node_A, \node_D\} \}.
\end{displaymath}
First, we consider the typical situation when all nodes are
functioning and available. To achieve the best possible control
quality in this case, it is important to synthesize a customized
solution (mapping, schedule, and controllers) that exploits the full
computation capacity of the platform to achieve as high control
quality as possible. Let us now consider that we only have time to
further synthesize mappings for two out of the four remaining feasible
configurations $\{\node_A,\node_B,\node_C\}$,
$\{\node_A,\node_B,\node_D\}$, $\{\node_B,\node_C,\node_D\}$, and
$\{\node_B,\node_C,\node_D\}$.  Considering the configurations
$\{\node_A,\node_B,\node_C\}$ and $\{\node_A,\node_B,\node_D\}$, we
shall discuss how to improve the control quality on top of what is
provided by the base configurations. Towards this, we have synthesized
solutions for the base configurations, as well as configurations
$\{\node_A,\node_B,\node_C\}$ and $\{\node_A,\node_B,\node_D\}$. We
have considered an example system that controls five inverted
pendulums. Table~\ref{tab:configurationcosts} shows the obtained
control costs (Equation~\ref{eq:overallcontrolcost}). We remind that a
small cost indicates high control quality, and vice versa.
Considering that a mapping for $\{\node_A,\node_B,\node_C\}$ would not
have been generated, then in that configuration the system can only
run with the mapping for base configuration $\{\node_A,\node_C\}$ or
$\{\node_B,\node_C\}$ with costs 5.3 and 7.5, respectively. Because of
its better control quality, the system would use the mapping for
$\{\node_A,\node_C\}$ (with cost 5.3) when in configuration
$\{\node_A,\node_B,\node_C\}$. By generating a customized solution,
however, we can achieve a better control quality in that configuration
according to the obtained cost~4.3 (a cost improvement of~1.1).

If a customized solution is not generated for configuration
$\{\node_A,\node_B,\node_D\}$, the system uses the mapping (and the
corresponding schedules and controllers) for $\{ \node_A,\node_D\}$
and does not utilize the computation capacity of $\node_B$ to achieve
a better control quality than what is achieved in the base
configuration.  By generating a customized solution, we can decrease
the control cost by 3.3 for the case that $\node_C$ has failed (a
control-quality improvement of 51.6 percent).  The particular
selection of the two configurations $\{\node_A,\node_B,\node_C\}$ and
$\{\node_A,\node_B,\node_D\}$ to consider in this example is done
depending on failure probabilities of the nodes in the system, as well
as the potential improvement in control quality upon the minimum level
provided by the base configurations. We shall elaborate on this
selection in more detail in Section~\ref{sec:heuristic}.


\begin{table}
  \caption{Task mapping for three configurations and three control applications.
  Each row shows tasks that run on a certain node in a given configuration.}
  \label{tab:taskmappings}
  \centering  
  \begin{tabular}{@{}c@{}c@{}c@{}c@{}}
    \hline
    $\nodeconfig$ & $\node_A$ & $\node_B$ & $\node_C$  \\
    \hline
    $\{\node_A,\node_C\}$ & $\task_{11}, \task_{21}, \task_{31}, \task_{12}$ & -- & $\task_{22}, \task_{32}, \task_{13}, \task_{23}, \task_{33}$ \\
    
    %    $\{\node_B,\node_C\}$ & -- & $\task_{12}, \task_{22}$ & $\task_{11}, \task_{21}, \task_{31}, \task_{32}, \task_{13}, \task_{23}, \task_{33}$ \\
    
    $\{\node_B,\node_C\}$ & -- & $\task_{12}, \task_{22}$ & $\task_{11}, \task_{21}, \task_{31}, \task_{32}$ \\
    & & & $\task_{13}, \task_{23}, \task_{33}$ \\
    
    $\{\node_A,\node_B,\node_C\}$ & $\task_{11}, \task_{21}, \task_{31}$ & $\task_{12}, \task_{22}, \task_{32}$ & $\task_{13}, \task_{23}, \task_{33}$ \\
    \hline
  \end{tabular}
\end{table}


Once solutions for additional configurations have been synthesized, it
must be verified whether it is possible to adapt to these solutions if
faults occur at runtime. Thus, for the two additional mappings in our
example, we must check whether these can be realized if nodes fail
during operation. In Table~\ref{tab:taskmappings}, we show the mapping
for the first configuration $\{\node_A,\node_B,\node_C\}$, as well as
the mappings of its corresponding base configurations
$\{\node_A,\node_B\}$ and $\{\node_B,\node_C\}$.  For the base
configurations, we consider that the tasks are stored on the
corresponding computation nodes. For example, the tasks in the column
for $\node_A$, corresponding to the two base configurations, are
stored on node $\node_A$. We also note that tasks $\task_{12}$ and
$\task_{22}$ are stored on $\node_B$. Let us consider the mapping of
the tasks to the configuration $\{\node_A,\node_B,\node_C\}$. We note
that all tasks except for $\task_{32}$ are already stored on the
corresponding nodes to realize the mapping for
$\{\node_A,\node_B,\node_C\}$. Task $\task_{32}$ is stored on
$\node_C$ and thus, needs to be migrated to $\node_B$ in order to
realize the mapping at runtime.  Note that the program state does not
need to be transferred during task migration due to the nature of
feedback-control applications (the state is automatically restored by
the control algorithm at the first sampling and measurement instant
directly after task migration has completed). The migration time
cannot exceed specified bounds, in order to guarantee
stability.\footnote{Other design objectives can also contribute to the
  maximum time allowed for migration. For example, during migration,
  the plants may be controlled by dedicated components with high
  sampling and actuation rates and for which component aging cannot be
  neglected. Then, it is very costly to use these components for a
  longer period of time. High actuation rates also cause more wear on
  physical actuators.}  Hence, if the migration time for $\task_{32}$
satisfies the specified bounds, we can realize the configuration
$\{\node_A,\node_B,\node_C\}$. Similarly, we have a mapping for the
other selected feasible configuration
$\{\node_A,\node_B,\node_D\}$. By considering this mapping and the
mapping for the only base configuration $\{\node_A,\node_D\}$ that can
be used to operate the system in configuration
$\{\node_A,\node_B,\node_D\}$, it may turn out that several tasks need
to be migrated to $\node_B$. If the time required to migrate these
tasks at runtime exceeds the given bounds, then the mapping for
$\{\node_A,\node_D\}$ is used at runtime with control cost~6.4 without
using the available node $\node_B$.  Alternatively, more memory can be
used to store additional tasks $\node_B$, in order to realize the
mapping at runtime without or with less task migration. In this way,
we avoid the excessive amount of migration time and we can realize the
mapping, although at the cost of larger required memory space on
$\node_B$ to achieve the better control cost~3.1 in configuration
$\{\node_A,\node_B,\node_D\}$. In the following subsection, we present
a formal statement of the design space exploration. Thereafter, we
present an optimization approach that synthesizes selected
configurations and considers the trade-off between control quality and
memory cost.


\subsection{Problem statement} \label{sec:problemstatement}
\noindent
Given is a distributed platform with computation nodes $\nodeset$, a
set of plants $\plants$, and their control applications
$\applicationset$.  We consider that a task mapping
$\mapping_\nodeconfig : \taskset_\applicationset \longrightarrow
\nodeconfig$ has been generated for each base configuration
$\nodeconfig \in \baseconfigset$ as discussed in
Section~\ref{sec:base}.  We consider that tasks are stored permanently
on appropriate computation nodes to realize the task mappings for the
base configurations (i.e., no task migration is needed at runtime to
adapt to solutions for base configurations). Thus, to realize the
mappings for base configurations, each task $\task \in
\taskset_\applicationset$ is stored on nodes
\begin{displaymath}
\bigcup_{\nodeconfig \in
  \baseconfigset} \{\mapping_\nodeconfig(\task)\}.
\end{displaymath}
The set of tasks that are stored on node $\node_d \in \nodeset$ is
\begin{displaymath}
  \storedtasks_d = \bigcup_{\nodeconfig \in \baseconfigset}
  \left\{
  \task \in \taskset_\applicationset : \mapping_\nodeconfig(\task) = \node_d
  \right\}.
\end{displaymath}
In addition, the inputs specific to the optimization step discussed in
this section are
\begin{compactitem}
\item the time $\migrationtime(\task)$ required to migrate task
    $\task$ from a node to any other node in the platform,
\item the maximum amount of time $\migrationtimemax_i$ that a plant 
    $\plant_i$ can stay in open loop without leading to instability~\cite{tabuada07tac} or
    degradation of control quality below a specified, minimum
    threshold (migration-time constraint), 
\item the memory space $\mem_d(\task)$ required to store task $\task
    \in \taskset_\applicationset$ on node $\node_d$ ($d \in
    \indexset_\nodeset$),
\item the additional available memory $\maxmemory_d$ of each node
    $\node_d$ in the platform to store information related to the
    tasks and messages of the system (note that this does not include
    the memory consumed for the base configurations as these are
    mandatory to implement and sufficient dedicated memory is assumed
    to be provided), and
\item the failure probability $\failureprob(\node)$ for each node
$\node \in \nodeset$.
\end{compactitem}
The failure probability $\failureprob(\node)$ depends on the mean time
to failure (MTFF) of the computation node. The MTFF is decided by the
technology of the production process, the ambient temperature of the
components, and voltage or physical shocks that the components may
suffer in the operational environment of the
system~\cite{korenFTbook}. The decision variables of the optimization
problem are a subset of configurations $\mappedconfigset \subseteq
\feasibleconfigset \setminus \baseconfigset$ and a mapping
$\mapping_\nodeconfig$ for each $\nodeconfig \in \mappedconfigset$
with a customized schedule and controllers~\cite{blind}. Thus, in
addition to the base configurations, we generate mappings for the
other feasible configurations $\mappedconfigset$. We require that
$\nodeset \in \mappedconfigset$, which means that it is mandatory to
generate solutions for the case when all nodes in the system are
operational.




%%%%%%%%%%%%%%%%%
% Cost function %
%%%%%%%%%%%%%%%%%
Let us now define the cost that characterizes the overall control
quality of the system in any feasible configuration based on the
solutions (mappings, schedules, and controllers) for the selected set
of configurations. We shall first associate a cost
$\controlcost^\nodeconfig$ for each feasible configuration
$\nodeconfig \in \feasibleconfigset$.  If $\nodeconfig \in
\baseconfigset \cup \mappedconfigset$, a customized mapping for that
configuration has been generated with a cost
$\controlcost^\nodeconfig$ given by
Equation~\ref{eq:overallcontrolcost}. If $\nodeconfig \notin
\baseconfigset \cup \mappedconfigset$ and $\nodeconfig \in
\feasibleconfigset$, then at runtime we use the mapping of a
configuration $\nodeconfig^\prime$ for which $\nodeconfig^\prime \in
\baseconfigset \cup \mappedconfigset$ and $\nodeconfig^\prime \subset
\nodeconfig$. It is guaranteed that such a configuration
$\nodeconfig^\prime$ can be found in the set of base configurations
$\baseconfigset$ (see Section~\ref{sec:base}).  If such a
configuration is included in $\mappedconfigset$, then the control
quality is better than in the corresponding base configuration because
of better utilization of the available computation nodes. Thus, for
the case $\nodeconfig \notin (\baseconfigset \cup \mappedconfigset)
\cap \feasibleconfigset$, the cost of the feasible configuration
$\nodeconfig$ is
\begin{equation}
  \controlcost^\nodeconfig =
  \min_{
    \begin{array}{cc}
      \nodeconfig^\prime \in \baseconfigset \cup \mappedconfigset\\
      \nodeconfig^\prime \subset \nodeconfig
    \end{array}
  }
  \controlcost^{\nodeconfig^\prime},
  \label{eq:inheritedcost}
\end{equation}
which means that the best available and functionally correct solution,
in terms control quality, is used to operate the system in
configuration $\nodeconfig$. The cost to minimize when selecting the
set of additional feasible configurations $\mappedconfigset \subseteq
\feasibleconfigset \setminus \baseconfigset \setminus \{\nodeset\}$ to
synthesize is defined
\begin{equation}
\label{eq:dseCost}
  \controlcost = 
  \sum_{\nodeconfig \in \feasibleconfigset \setminus \baseconfigset \setminus \{\nodeset\}}
  \failureprob^\nodeconfig \controlcost^\nodeconfig
  ,
\end{equation}
where $\failureprob^\nodeconfig$ is the probability of node failures
that lead the system to configuration $\nodeconfig$. Towards this, we
shall consider the given failure probabilities of the computation
nodes. For each node $\node \in \nodeset$, we have a given failure
probability $\failureprob(\node)$. The cost in
Equation~\ref{eq:dseCost} characterizes the control quality of the
system depending on the additional feasible configurations for which
solutions have been synthesized. If solutions are available only for
the set of base configurations, the system tolerates all
designer-specified node failures, but typically at a large cost
$\controlcost$ (Equation~\ref{eq:dseCost}). This is because other
feasible configurations operate at runtime with solutions of base
configurations. In those situations, all available computation nodes
are not utilized at the cost of reduced overall control quality. By
synthesizing solutions for additional feasible configurations, the
cost in Equation~\ref{eq:dseCost} is reduced (i.e., overall control
quality is improved) due to the cost reduction in the terms related to
the selected set of configurations.



\subsection{Optimization approach} \label{sec:heuristic}
\noindent
Figure~\ref{fig:overview} shows an overview of our proposed design
approach. The first component, which we discussed in
Section~\ref{sec:base}, is the identification and mapping synthesis of
base configurations. The second component comprises the exploration
and synthesis of additional configurations, as well as 
mapping-realization step that considers the constraints related to
task migration and memory space.


\begin{figure}
  \centering
%  \includegraphics[width=0.2\textwidth,angle=90]{figures/overview}
  \includegraphics[width=0.2\textwidth]{figures/overview}
  \caption{Overview of our design framework.
  The first step is to construct solutions for the set of base configurations to achieve fault-tolerance and a minimum control-quality level. In the second step, the system is further optimized for additional configurations.}
  \label{fig:overview}
\end{figure}


\subsubsection{Exploration of the set of configurations} \label{sec:exploration}
\noindent
Our optimization heuristic is designed to minimize the cost in
Equation~\ref{eq:dseCost} and is based on a priority-based search of
the Hasse diagram of configurations. The priorities are computed
iteratively as a step of the optimization process based on
probabilities for the system to reach configurations.  The heuristic
belongs to the class of anytime algorithms, meaning that it can be
stopped at any point in time and return a feasible solution. The
quality of the solution is improved as more design time is invested.


Initially, as a mandatory step, we synthesize a mapping for the
configuration $\nodeset$, in order to support the execution of the
control system for the case when all computation nodes are
operational. During the exploration process, a priority queue with
configurations is maintained. Whenever a mapping
$\mapping_\nodeconfig : \taskset_{\applicationset} \longrightarrow
\nodeconfig$ has been synthesized for a certain 
configuration $\nodeconfig \in \feasibleconfigset$ (note that $\nodeset$ is the first 
synthesized configuration), each feasible
configuration $\nodeconfig^\prime \subset \nodeconfig$ with
$\setsize{\nodeconfig^\prime} = \setsize{\nodeconfig} - 1$ is added to
the priority queue with priority equal to the probability
\begin{equation}
\failureprob^{\nodeconfig^\prime} = \failureprob^\nodeconfig
\failureprob(\node),
\label{eq:failureprobability}
\end{equation}
where $\{\node\} = \nodeconfig \setminus
\nodeconfig^\prime$. For the initial configuration $\nodeset$, 
we consider $\failureprob^\nodeset = 1$.
If two configurations have the same probability, we give priority to
the one that has the worse control quality in the
corresponding base configuration.

Subsequently, for configuration $\nodeconfig$, we check whether it is possible to realize the generated
mapping $\mapping_\nodeconfig : \taskset_{\applicationset} \longrightarrow
\nodeconfig$ at runtime with task
migration and the available additional memory to store tasks. This
step is described in detail in the next subsection 
(Section~\ref{sec:mappingrealization}). If this step
succeeds, it means that the mapping can be realized at runtime and we thus
add $\nodeconfig$ to the set $\mappedconfigset$ (this set
is initially empty). Further in that case, for each node $\node_d$, the set of tasks
$\storedtasks_d$ stored on $\node_d$ and the amount of additional
consumed memory $\mem_d$ is updated. 
If the mapping realization did not succeed, it means that a solution for a base configuration
must be used at runtime to operate the system in the feasible configuration $\nodeconfig$.
Independently of whether the
mapping realization of $\nodeconfig$ succeeded, the exploration continues by
generating a solution for the next configuration in the maintained
priority queue of configurations. The exploration terminates when the
additional memory on all computation nodes has been consumed or a
specified design time has passed (e.g., the designer stops the exploration process).
The next section presents the mapping realization step that deals with the memory
and migration-time constraints for a given mapping of a configuration.


\subsubsection{Mapping realization} \label{sec:mappingrealization}
\noindent
In the previous subsection (Section~\ref{sec:exploration}),
we proposed a search order to explore and synthesize solutions for feasible configurations
additional to the set of base configurations.
For each configuration $\nodeconfig \in \feasibleconfigset \setminus
\baseconfigset$ that is considered in the exploration process, a mapping
$\mapping_\nodeconfig : \taskset_\applicationset \longrightarrow
\nodeconfig$ is constructed (along with customized schedules and controllers).
We shall in the remainder of this section focus on whether and how this mapping can be realized
at runtime in case the system reaches configuration $\nodeconfig$.
We first check whether there is
sufficient memory to store information related to the solution (mapping, schedules, and controllers)
for the configuration. The required memory for this information
is denoted $\mem_{d}^{\nodeconfig}$ and is an output of the mapping and synthesis step for configuration
$\nodeconfig$ (Section~\ref{sec:mapping}). Let us denote with $\mem_d$
the amount of additional memory that is already consumed on $\node_d$
for other configurations in $\mappedconfigset \subset
\feasibleconfigset \setminus \baseconfigset$.  If 
\begin{displaymath}
\mem_d + \mem_d^\nodeconfig > \maxmemory_d
\end{displaymath}
for some $d \in \indexset_\nodeset$,
it means that the information related to mapping, schedules, and controllers for
configuration $\nodeconfig$ cannot be stored on the
computation platform. For such cases, we declare that the mapping
$\mapping_\nodeconfig$ cannot be realized (we remind that 
solutions for base configurations, however, 
can be used to operate the system in configuration $\nodeconfig$).

If the solution for $\nodeconfig$ can be stored within the given
memory limit, we check whether migration of tasks that are needed to
realize the mapping can be done within the maximum allowed migration
time $\migrationtimemax$.  The total migration time must not exceed
the maximum allowed migration time\footnote{Instead of
  constraining the total migration time, we may consider
  that base configurations are used to operate the system while task
  migrations are performed in the available time slack of the
  communication channel. The problem is then to schedule task
  migrations together with all messages in the base configuration such
  that the total migration time is minimized.}
\begin{displaymath}
\migrationtimemax =
\min_{i \in \indexset_\plants} \migrationtimemax_i.
\end{displaymath}
We consider that the time to detect that a node has failed is
considered by the designer when specifying the maximum allowed
migration time. If the migration-time constraint cannot be met, we
reduce the migration time below the threshold $\migrationtimemax$ by
storing tasks in the memory of computation nodes (this memory
consumption is additional to those tasks stored to realize base
configurations).  The main idea is to store as few tasks as possible
to satisfy the migration-time constraint.  Towards this, let us
consider the set of tasks
\begin{displaymath}
  \migratedtasks_d(\nodeconfig) = \left\{
  \task \in \taskset_\applicationset \setminus \storedtasks_d :
  \mapping_\nodeconfig(\task) = \node_d
  \right\}
\end{displaymath}
that need to be migrated to node $\node_d$ at runtime in order to
realize the mapping $\mapping_\nodeconfig$, given that
$\storedtasks_d$ is the set of tasks that already are stored on node
$\node_d$.
 
The objective is to find a set of tasks $\selectedtaskstostore_d
\subseteq \migratedtasks_d(\nodeconfig)$ to store for each $\node_d
\in \nodeset$ such that the memory consumption is minimized and 
the maximum allowed migration time is considered. We formulate this
problem as an integer linear program (ILP) by introducing a binary
variable $\taskboolean_d^\task$ for each node $\node_{d} \in \nodeset$
and each task in $\migratedtasks_d(\nodeconfig)$. Task
$\task \in \migratedtasks_d(\nodeconfig)$ is stored on $\node_d$ if
$\taskboolean_d^\task = 1$, and migrated if $\taskboolean_d^\task =
0$. The memory constraint is thus formulated as
\begin{equation}
	\mem_d + \mem_d^\nodeconfig + \sum_{\task \in \migratedtasks_d(\nodeconfig)} \taskboolean_d^\task\mem_d(\task)
	\leqslant \maxmemory_d,
	 \label{eq:memconstr}
\end{equation}
which models that the memory consumption $\mem_d^\nodeconfig$ of
the solution together with
the memory needed to store the selected tasks do not exceed the memory limitations.
The migration-time constraint is formulated similarly as
\begin{equation}
	\sum_{d \in \indexset_\nodeset} \left( \sum_{\task \in \migratedtasks_d(\nodeconfig)} 
	(1 -\taskboolean_d^\task )\migrationtime(\task) \right)
        \leqslant \migrationtimemax.
	\label{eq:migrationconstr}
\end{equation}
The memory cost to minimize in the selection of
$\selectedtaskstostore_d \subseteq \migratedtasks_d(\nodeconfig)$ is
given by
\begin{equation}
	 \sum_{d \in \indexset_\nodeset} \left( \sum_{\task \in  \migratedtasks_d(\nodeconfig)} \taskboolean_d^\task\mem_d(\task) \right).
	\label{eq:realizationobjective}
\end{equation}
If a solution to the ILP formulation cannot be found, then the mapping
cannot be realized.  If a solution is found, we have
\begin{displaymath}
\selectedtaskstostore_d = \{ \task \in \migratedtasks_d(\nodeconfig)
: \taskboolean_d^\task = 1\}
\end{displaymath}
and we update the set $\storedtasks_d$
and the memory consumption $\mem_d$, respectively, according to
\begin{displaymath}
\storedtasks_d \algAssignment \storedtasks_d \cup
\selectedtaskstostore_d
\end{displaymath}
and
\begin{displaymath}
	\mem_d \algAssignment
	\mem_d + \mem_d^\nodeconfig + \sum_{\task \in \selectedtaskstostore_d} \mem_d(\task).
\end{displaymath}
For large systems, the ILP given by Equations~\ref{eq:realizationobjective},
\ref{eq:memconstr}, and~\ref{eq:migrationconstr}
can be solved optimally and efficiently
with modern solvers. We have used the \texttt{eplex} library for ILP
in \eclipse~\cite{clpbook}, and it incurred neglectable time-overhead
(up to 1 second) for systems with 60 tasks in our experiments.


